package ljl.codetop300;

/**
 * 这个题没什么技巧应该，就是迭代，找规律，找变化量和不变量
 * 挺难的
 */
public class _400_find_nth_digit {

  /**
   * 过了居然，不过还是得看看其他人怎么写的，这一步很关键
   * 宽度 1 - 1 2 3 4 5 6 7 8 9 - 9 个
   * 宽度 2 - 10 11 12 13 14 15 16 17 18 19 20 21 22 ... 99 - 90 个
   * 宽度 3 - 100 101 ... 999 - 900 个
   * 宽度 4 - 1000 1001 9999 - 9000 个
   */
  static class tet {
    public static void main(String[] args) {
      System.out.println(new tet().findNthDigit(10000));
    }
    public int findNthDigit(int n) {
      int width = 1;
      int tens = 0;
      int num = 0;
      while (n > width * Math.pow(10, tens) * 9) {
        int inc = (int) Math.pow(10, tens) * 9;
        num += inc;
        n -= width * inc;
        width++;
        tens++;
      }
      num += n / width;
      int remainder = n % width;
      if (remainder != 0) {
        num++;
        String str = String.valueOf(num);
        return str.charAt(remainder - 1) - '0';
      }
      return String.valueOf(num).charAt(width - 1) - '0';
    }
  }

  static class off1 {
    public int findNthDigit(int n) {
      int d = 1, count = 9;
      /**
       * 这还有个陷阱，得是 long，可能溢出
       */
      while (n > (long) d * count) {
        n -= d * count;
        d++;
        count *= 10;
      }
      int index = n - 1;
      int start = (int) Math.pow(10, d - 1);
      int num = start + index / d;
      int digitIndex = index % d;
      int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
      return digit;
    }
  }

  /**
   * 死记硬背了一版
   */
  static class copy_off1 {
    public int findNthDigit(int n) {
      int width = 1, count = 9;
      while (n > (long) width * count) {
        n -= width * count;
        width++;
        count *= 10;
      }
      int start = (int) Math.pow(10, width - 1);
      int index = n - 1;
      int num = start + index / width;
      int indexInNum = index % width;
      return num / (int) Math.pow(10, width - (indexInNum + 1)) % 10;
    }
  }

  /**
   * 二分思路也不错
   */
  static class bisect {
    public int findNthDigit(int n) {
      int low = 1, high = 9;
      while (low < high) {
        int mid = (high - low) / 2 + low;
        if (totalDigits(mid) < n) {
          low = mid + 1;
        } else {
          high = mid;
        }
      }
      int d = low;
      int prevDigits = totalDigits(d - 1);
      int index = n - prevDigits - 1;
      int start = (int) Math.pow(10, d - 1);
      int num = start + index / d;
      int digitIndex = index % d;
      int digit = (num / (int) (Math.pow(10, d - digitIndex - 1))) % 10;
      return digit;
    }

    public int totalDigits(int length) {
      int digits = 0;
      int curLength = 1, curCount = 9;
      while (curLength <= length) {
        digits += curLength * curCount;
        curLength++;
        curCount *= 10;
      }
      return digits;
    }
  }

  /**
   * 我都不想写了，前面通过二分找到了之前的位数、宽度，其实没什么乱用，后面和解法一一样
   */
  static class copy_bisect {
    public int findNthDigit(int n) {
      int min = 1, max = 9;
      while (min < max) {
        int mid = (min + max) / 2;
        if (totalDigits(mid) < n) min = mid + 1;
        else max = mid;
      }
      int d = min;
      int lastWidthTotalDigits = totalDigits(d - 1);
      int start = (int) Math.pow(10, d - 1);
      n -= lastWidthTotalDigits + 1;
      int index = n % d;
      int num = start + n / d;
      return num / (int) Math.pow(10, d - (index + 1)) % 10;
    }
    int totalDigits(int max) {
      int d = 1, count = 9;
      int digits = 0;
      while (d <= max) {
        digits += d * count;
        d++;
        count *= 10;
      }
      return digits;
    }
  }
}
